package com.eistert.java.algorithm.dijkstra;

import java.util.Arrays;

/**
 * 迪杰斯特拉算法
 * 应用场景-最短路径问题
 *
 * @Author: ai
 * @create: 2023-04-26 10:53
 */
public class VisitedVertex {
    /**
     * 问题背景
     * 1)战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到A, B, C , D, E, F 六个村庄。
     *2)各个村庄的距离用边线表示(权) ，比如 A – B  距离 5 公里
     *3)问：如何计算出 G 村庄到 其它各个村庄的最短距离?
     *4)如果从其它点出发到各个点的最短距离又是多少?
     *
     *
     * 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。
     * 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
     *
     *
     */

    /**
     * 迪杰斯特拉(Dijkstra)算法过程
     * <p>
     * 1)设置出发顶点为 v，顶点集合 V{v1,v2,vi...}，v 到 V 中各顶点的距离构成距离集合 Dis，Dis{d1,d2,di...}，
     * Dis集合记录着 v 到图中各顶点的距离(到自身可以看作 0，v 到 vi 距离对应为 di)。
     * <p>
     * 2)从 Dis 中选择值最小的 di 并移出 Dis 集合，同时移出 V 集合中对应的顶点 vi，此时的 v 到 vi 即为最短路径。
     * <p>
     * <p>
     * 3)更新 Dis 集合，更新规则为：比较 v 到 V 集合中顶点的距离值，与 v 通过 vi 到 V 集合中顶点的距离值，
     * 保留值较小的一个(同时也应该更新顶点的前驱节点为 vi，表明是通过 vi 到达的)。
     * <p>
     * 4)重复执行两步骤，直到最短路径顶点为目标顶点即可结束
     */

    /**
     * 记录各个顶点是否访问过.
     * 1 表示访问过,0 未访问,会动态更新
     */
    private int[] already_arr;

    /**
     * 每个下标对应的值为前一个顶点下标, 会动态更新
     */
    public int[] pre_visited;

    /**
     * 记录出发顶点到其他所有顶点的距离,比如 G 为出发顶点，
     * 就会记录 G 到其它顶点的距离，会动态更新，
     * 求的最短距离就会存放到 dis
     */
    public int[] dis;


    /**
     * 构造器
     *
     * @param length
     * @param index
     */
    public VisitedVertex(int length, int index) {
        this.already_arr = new int[length];

        this.pre_visited = new int[length];

        this.dis = new int[length];

        // 初始化 dis 数组
        Arrays.fill(dis, 65535);

        // 设置出发顶点被访问过
        this.already_arr[index] = 1;

        // 设置出发顶点的访问距离为0
        this.dis[index] = 0;
    }


    /**
     * 功能: 判断 index 顶点是否被访问过
     *
     * @return 如果访问过，就返回 true,  否则访问 false
     */
    public boolean in(int index) {
        return already_arr[index] == 1;
    }

    /**
     * 功能: 更新出发顶点到 index 顶点的距离
     *
     * @param index
     * @param len   出发顶点到index顶点的距离
     */
    public void updateDis(int index, int len) {
        dis[index] = len;
    }

    /**
     * 功能: 更新 pre 这个顶点的前驱顶点为 index 顶点
     *
     * @param pre
     * @param index
     */
    public void updatePre(int pre, int index) {
        pre_visited[pre] = index;
    }


    /**
     * 功能:返回出发顶点到 index 顶点的距离
     *
     * @param index
     * @return
     */
    public int getDis(int index) {
        return dis[index];
    }


    /**
     * 继续选择并返回新的访问顶点， 比如这里的 G 完后，
     * 就是 A 点作为新的访问顶点(注意不是出发顶点)
     */
    public int updateArr() {

        int min = 65535, index = 0;

        for (int i = 0; i < already_arr.length; i++) {
            if (already_arr[i] == 0 && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }

        // 更新index顶点被访问过
        already_arr[index] = 1;
        return index;
    }

    /**
     * 显示最后的结果
     * 即将三个数组的情况输出
     */
    public void show() {

        System.out.println("==================");
        // 输出 already_arr
        for (int i : already_arr) {
            System.out.print(i + "");
        }
        System.out.println();

        // 输出pre_visited
        for (int i : pre_visited) {
            System.out.println(i + "");
        }

        System.out.println();


        // 输出dis
        for (int i : dis) {
            System.out.println(i + "");
        }

        System.out.println();

        // 为了好看最后的最短距离，我们处理一下
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        int count = 0;
        for (int i : dis) {
            if (i != 65535) {
                System.out.print(vertex[count] + "(" + i + ") ");
            } else {
                System.out.println("N ");
            }

            count++;
        }
        System.out.println();
    }
}
